package com.lzq.leetcode.hoot100;

import java.util.Deque;

public class s4 {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int len = len1 + len2;
        if (len % 2 == 1) {
            return findK(nums1, nums2, len/2+1);
        } else {
            return ( findK(nums1, nums2, len/2) + findK(nums1, nums2, len/2+1) ) / 2.0;
        }
    }

    private int findK(int[] nums1, int[] nums2, int k) {

        int pos1 = 0, pos2 = 0;
        while (true) {

            if (pos1 == nums1.length) {
                return nums2[pos2 + k - 1];
            }

            if (pos2 == nums2.length) {
                return nums1[pos1 + k - 1];
            }

            if (k == 1) {
                return Math.min(nums1[pos1], nums2[pos2]);
            }

            int mid = k / 2;
            int tp1 = Math.min(nums1.length, pos1+mid)-1;
            int tp2 = Math.min(nums2.length, pos2+mid)-1;
            if (nums1[tp1] < nums2[tp2]) {
                k -= tp1 - pos1 + 1;
                pos1 = tp1 + 1;
            } else {
                k -= tp2 - pos2 + 1;
                pos2 = tp2 + 1;
            }

        }
    }

    public static void main(String[] args) {
        System.out.println(new s4().findMedianSortedArrays(new int[]{1, 2}, new int[]{3, 4}));
    }
}
